import java.util.*;

/**
* @description: 2035. 将数组分成两个数组并最小化数组和的差
* @author hewei
* @date 2022/8/21 08:39
* @version 1.0
*/

public class MinimumDifference {

    public static void main(String[] args) {
        MinimumDifference minimumDifference = new MinimumDifference();
        int[] nums = {3,9,7,3};
        System.out.println(minimumDifference.minimumDifference(nums));
    }

    HashMap<Integer, List<Integer>> map1;
    HashMap<Integer, List<Integer>> map2;
    public int minimumDifference(int[] nums) {
        map1 = new HashMap<>();
        map2 = new HashMap<>();
        int n = nums.length;
        process(0, nums, 0, 0);
        process1(n / 2, nums, 0, 0);
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        int ans = Integer.MAX_VALUE;
        for (Map.Entry<Integer, List<Integer>> entry : map1.entrySet()) {
            int count = entry.getKey();
            List<Integer> sums = entry.getValue();
            List<Integer> list = map2.get(n / 2 - count);
            Collections.sort(list);
            double target = (double) sum / 2;
            for (Integer temp : sums) {
                int l = 0;
                int r = list.size() - 1;
                while (l < r) {
                    int mid = (r - l) / 2 + l;
                    if (list.get(mid) + temp < target) {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                }
                ans = Math.min(ans, Math.abs(sum - temp - list.get(l) - (temp + list.get(l))));
            }
        }
        return ans;
    }

    public void process(int i, int[] num, int count, int sum) {
        if (i == num.length / 2) {
            if (!map1.containsKey(count)) map1.put(count, new ArrayList<>());
            map1.get(count).add(sum);
            return;
        }
        process(i + 1, num, count, sum);
        process(i + 1, num, count + 1, sum + num[i]);
    }

    public void process1(int i, int[] num, int count, int sum) {
        if (i == num.length) {
            if (!map2.containsKey(count)) map2.put(count, new ArrayList<>());
            map2.get(count).add(sum);
            return;
        }
        process1(i + 1, num, count, sum);
        process1(i + 1, num, count + 1, sum + num[i]);
    }
}